The present invention is a method for efficiently producing computer generated two-dimensional synthetic images of three-dimensional scenes. Computer graphics research has explored a variety of techniques for the creation of realistic, yet simulated images. In this context, a realistic image would be an image indistinguishable from a photograph of a real, three-dimensional scene. As research has progressed, the continual inclusion of more and more features of real scenes within image generation algorithms (features such as opacity, surface textures, soft shadows) has led to increasingly realistic images.
One of the first successful image synthesis approaches started with the basic physics of lens design. To design and investigate lens properties, one often plots the path taken by rays of light starting at a light source, which then pass through the lens to a focal point. The process of following the light rays is called ray tracing. However, when first developed, the method of ray tracing were computationally intensive and impractical for existing computer resources. Instead, other methods were explored to handle the various different components of image synthesis, such as reflections, shadows, motion blur of fast-moving objects, etc. However, most of these other techniques worked only for special cases and were not easily combined together. Hence, synthetic images might have shadows, but no transparent objects, or reflections but no motion blur.
As increasingly powerful and inexpensive computers evolved, ray tracing algorithms received greater attention. Simulating the actual physics of image generation, through substantial numbers of calculations, became practical and attractive for image synthesis. The methods of ray-tracing algorithms have been augmented with powerful techniques for handling many different kinds of optical phenomena. Current ray-tracing techniques are relatively simple, elegant and easily implemented.
Ray tracing starts with a few basic elements: a three-dimensional scene lit by one or more light sources, a viewing screen comprising an array of pixel elements (a window onto the scene), and a hypothetical viewing eye which looks out on the scene through the viewing screen. The goal of any image synthesis technique is to correctly color each pixel of the viewing screen such that looking at the screen from the vantage of the hypothetical eye would recreate the original three-dimensional scene as closely as possible.
If one uses the actual physics of image generation to trace rays (termed "forward ray tracing"), light emerging from the light sources strikes various objects and boundaries within the scene, often a number of times. Some of the light is absorbed, some is reflected away from the viewing screen, and some light actual strikes the screen through a pixel and enters the eye. This method of forward ray tracing, while it may seen the intuitively correct way to regenerate the scene, is prohibitively difficult and expensive to implement. The problem is that too many of the light rays generated by the light sources are useless: they never manage to reflect off of or pass through surfaces in exactly the way needed to pass through a pixel into the eye. Most of the computational time would be spent examining these useless light rays.
As generally implemented, ray tracing is really backward ray tracing, whereby a backward-going ray from the hypothetical viewing eye passes through a pixel on the viewing screen and strikes an object within the scene to be rendered. By working backwards, one asks the question: "if a ray of light went through this pixel into the eye, from where did it come and what color is it?" Having found the first surface which the backward ray struck, one wants the description of all light striking that point on that surface and then how the incident light is affected by the particular surface characteristics of the struck object. The combined light illumination of the object then can be passed back along the original ray through the particular pixel into the viewer's eye, allowing the pixel to be appropriately shaded. Of course, the different intensities, directions, colors and origins of the light striking the point on the object's surface is infinite; path tracing seeks to sample the light coming from different sources efficiently so that a few samples can replace exhaustively looking at all light rays, while still recovering enough useful information to construct a close estimate of the scene's photometry.
Ray tracing methods are recursive: to find the illumination at a particular object's surface struck by the first backward ray, other backward rays are sent from the object. These rays might strike light sources, providing direct illumination of the surface, or might strike other objects, providing indirect reflected and transmitted light. There are two important problems faced by ray tracing methods. First, because backward-going rays can be continued indefinitely one needs a way of determining when the estimated light incident on a surface is reliable within a certain confidence range. The requirement can be extended to determining when enough rays have been sent through each pixel onto the scene to accurately color each pixel. Both statistical methods and screen-based, pixel assignment algorithms have been implemented to determine when to end each set of ray traces.
As in any form of signal processing, image-synthesis algorithms are also bothered by aliasing effects. Thus, the second principal problem facing ray tracing methods occurs when high-frequency elements in the scene masquerade (or alias) as lower frequency artifacts. A familiar example of aliasing is the moire patterns which occur when numerous thin stripes are viewed on the regular pixel arrays of a television screen, and create broader, lower-frequency stripes. If samples (or backward rays) are taken periodically across the screen at some regular spatial frequency, objects having higher spatial frequencies either can be missed entirely or create aliasing artifacts at lower spatial frequencies.
One technique for reducing aliasing effects in synthetic images (called distributed ray tracing) sends the backward rays from the screen in a Poisson distributed pattern. The random allocation of rays to spatial points on the screen helps to convert regular aliasing artifacts to noise, which is much more acceptable to the human visual system. Dithering and jittering method have been used with some success to randomly sample the image space. The same techniques are also employed in the other dimensions of image synthesis, such as the dimensions of time and light frequency. These methods are principally screen-based, that is, they approach the problem by adequately sampling the screen with backward-going rays distributed randomly in space, time and color.
As discussed above, the backward rays strike objects in the scene to find how to accurately shade that point. To do so, the methods must estimate the total incident light at that point. But incident light combines in a non-uniform way depending upon reflection and transmission functions; the methods attempt to nonuniformly sample the incident light, while at the same time cover the entire reflection and transmission hemispheres, to ensure that there are no large gaps in the sampled regions.
As an example of distributed ray tracing methods, a pixel may be shaded by sending n backward-going rays (or eye rays) through the pixel; each eye ray in the pixel receives a number from 1 to n. When ray number k intersects an object, it needs to generate one or more reflection rays (to sample light that reflected from another object and into the eye). The direction of each of these rays is generally taken from the k.sup.th entry of prototype list or template of n direction ranges. Then the exact direction is randomly selected from within that range. A similar process is followed for the transmitted rays. The idea is that when all n rays have been shot, all n regions of the reflection (and transmission) hemisphere will have been sampled. Of course, not all n eye rays will necessarily strike the same object location, so that only some of each location's particular hemisphere will be sampled.
Path tracing presents an alternative to distributed ray tracing, in which in addition to a ray sent to each of the light sources, only one further backward-going ray is sent from an object struck by the first ray. Based on some choice algorithm, the next ray may either be a reflection ray or a transmission ray. The method attempts to save on computational resources by focusing most effort on the early rays (i.e., the initial eye rays and shadow rays) and less on the second, third, etc. rays which bounce from object to object and contribute much less to the final image. Path tracing attempts to sample the reflection and transmission hemispheres as a natural result of many paths arriving at the object. The direction of each sample is chosen from a single reflection function maintained over the lifetime of all eye rays sent from a given pixel.
Both distributed ray tracing and path tracing, as practiced in the prior art, include a shared simplification: the reflectance and transmittance functions are assumed to be the same for all objects in the scene, and thus for all materials as well. The prior art, by picking directions in which to send transmission and reflection rays by reference to a common template list, risks inadequate sampling at the level of individual objects. Further, the directional sampling loses any of the reflection and transmission characteristics peculiar to each surface, since it refers only to a scene-wide template. Distributed ray tracing records the history of shot rays almost entirely at the screen; all previous sampling is forgotten when a new pixel is started. Path tracing uses a global history mechanism, whereby all rays are steered throughout the scene in accordance with a predetermined distribution. In both methods, object-specific reflectance and transmission distributions are ignored.
An improved method of sampling scene information of image synthesis should provide techniques for thoroughly sampling image characteristics in a practical amount of computational time. The method should account for object-specific distributions of reflectance and transmission and for light-source variations. In addition, the method should ensure that a full distribution of image information appropriate for each object can be sampled, without undue waste. The practical and efficient creation of accurate synthetic images from a wider, more realistic range of object and lighting characteristics provided by such a method would satisfy a long felt need within the computer image synthesis community.